package oj;

import java.util.Scanner;

public class Day25F {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            int n=sc.nextInt();
            int[] arr=new int[10000];
           arr[0]=1;
           arr[1]=2;
            for (int i = 2; i < arr.length ; i++) {
                arr[i]=(arr[i-1]+arr[i-2])%10000;
            }
            for (int i = 0; i < n; i++) {
                System.out.printf("%04d",arr[sc.nextInt()-1]);//格式化输出
            }
            System.out.println();
        }
    }
}
